//给定循环单调非递减列表中的一个点，写一个函数向这个列表中插入一个新元素 insertVal ，使这个列表仍然是循环升序的。 
//
// 给定的可以是这个列表中任意一个顶点的指针，并不一定是这个列表中最小元素的指针。 
//
// 如果有多个满足条件的插入位置，可以选择任意一个位置插入新的值，插入后整个列表仍然保持有序。 
//
// 如果列表为空（给定的节点是 null），需要创建一个循环有序列表并返回这个节点。否则。请返回原先给定的节点。 
//
// 
//
// 示例 1： 
//
// 
//
// 
//输入：head = [3,4,1], insertVal = 2
//输出：[3,4,1,2]
//解释：在上图中，有一个包含三个元素的循环有序列表，你获得值为 3 的节点的指针，我们需要向表中插入元素 2 。新插入的节点应该在 1 和 3 之间，插入之后
//，整个列表如上图所示，最后返回节点 3 。
//
//
// 
//
// 示例 2： 
//
// 
//输入：head = [], insertVal = 1
//输出：[1]
//解释：列表为空（给定的节点是 null），创建一个循环有序列表并返回这个节点。
// 
//
// 示例 3： 
//
// 
//输入：head = [1], insertVal = 0
//输出：[1,0]
// 
//
// 
//
// 提示： 
//
// 
// 0 <= Number of Nodes <= 5 * 10^4 
// -10^6 <= Node.val <= 10^6 
// -10^6 <= insertVal <= 10^6 
// 
//
// 
//
// 
// 注意：本题与主站 708 题相同： https://leetcode-cn.com/problems/insert-into-a-sorted-
//circular-linked-list/ 
//
// Related Topics 链表 👍 162 👎 0


package LeetCode.editor.cn;

/**
 * @author ldltd
 * @date 2025-04-11 20:24:54
 * @description LCR 029.循环有序列表的插入
 */
public class FourUeAj6{
	 public static void main(String[] args) {
	 	 //测试代码
	 	 FourUeAj6 fun=new FourUeAj6();
	 	 Solution solution = fun.new Solution();

	 }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
// Definition for a Node.
class Node {
    public int val;
    public Node next;

    public Node() {}

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, Node _next) {
        val = _val;
        next = _next;
    }
}

class Solution {
    public Node insert1(Node head, int insertVal) {
        //为空则造一个
        if(head==null) {
            Node node = new Node(insertVal);
            node.next=node;
            return node;
        }
        //一个就造首尾
        if(head.next==head){
            Node node = new Node(insertVal);
            head.next=node;
            node.next=head;
            return head;
        }
        Node curr=head;
        int count=0;
        while (true){
            if(curr.val<=insertVal&&curr.next.val>=insertVal){
                Node next = curr.next;
                curr.next=new Node(insertVal);
                curr.next.next=next;
                return head;
            }
            //计数循环，因为一开始从head开始，所以初值为1
            if(curr==head){
                count++;
            }
            //第一次循环时，如果遇到首尾的情况，说明序列中没有合适的位置
            //要么加在头要么在尾
            if(count==2&&curr.next.val<curr.val){
                Node next = curr.next;
                curr.next=new Node(insertVal);
                curr.next.next=next;
                return head;
            }
            //第三次循环，说明所有元素都是相等的，不存在严格的头尾，则随便插入
            if(count==3){
                Node next = curr.next;
                curr.next=new Node(insertVal);
                curr.next.next=next;
                return head;
            }
            curr=curr.next;
        }
    }
    public Node insert(Node head, int insertVal) {
        Node node = new Node(insertVal);
        if (head == null) {
            node.next = node;
            return node;
        }
        if (head.next == head) {
            head.next = node;
            node.next = head;
            return head;
        }
        Node curr = head, next = head.next;
        //只遍历一圈，如果所有元素相同最后就随便插入
        while (next != head) {
            if (insertVal >= curr.val && insertVal <= next.val) {
                break;
            }
            if (curr.val > next.val) {
                if (insertVal > curr.val || insertVal < next.val) {
                    break;
                }
            }
            curr = curr.next;
            next = next.next;
        }
        curr.next = node;
        node.next = next;
        return head;
    }

}
//leetcode submit region end(Prohibit modification and deletion)

}
